/*
 *  Copyright 2008-2009 NVIDIA Corporation
 *
 *  Licensed under the Apache License, Version 2.0 (the "License");
 *  you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */



#pragma once

/*
 *  Return true if CSR matrix A has a symmetric nonzero storage pattern and false otherwise.
 *
 *  Note: the matrix values are irrelevant, i.e. [0 1] is structurally symmetric
 *                                               [2 0]  
 */
#include <cusp/csr_matrix.h>
#include <cusp/transpose.h>

#include <thrust/scatter.h>
#include <thrust/sequence.h>
#include <thrust/sort.h>

#include <thrust/iterator/counting_iterator.h>

#include <cusp/detail/config.h>

namespace cusp
{
namespace graph
{

struct part_type {};
struct metis   : part_type{};
struct patoh   : part_type{};
struct blk     : part_type{}; // Block partitioning
struct wbk     : part_type{}; // Weighted-block partitioning
struct ran     : part_type{}; // Random partitioning

struct method_type {};
struct rowwise : method_type{}; // Row-wise partitioning
struct colwise : method_type{}; // Column-wise partitioning

/*! \addtogroup algorithms Algorithms
 *  \ingroup algorithms
 *  \{
 */

/*! \p Uses METIS to partition a graph 
 * \param graph symmetric matrix that represents a graph
 *
 * \tparam IndexType int
 * \tparam ValueType float
 *
 */

////////////////////////////////////////////////////////////////////////////////
//! Partition a graph given in csr_matrix format into a given number of parts
//!
//!  Note: IndexType must be 'int' or 'unsigned int'
//!
////////////////////////////////////////////////////////////////////////////////

template <typename PartitionerType, typename MethodType,
	  typename MatrixType, typename ArrayType >
size_t partition(const MatrixType& graph, 
                       size_t num_parts,  
                       ArrayType& part,                 
                       bool Kway = false);

/*! \}
 */

/*
 *  Return true if CSR matrix A has a symmetric nonzero storage pattern and false otherwise.
 *
 *  Note: the matrix values are irrelevant, i.e. [0 1] is structurally symmetric
 *                                               [2 0]
 */
template <class IndexType, class ValueType, class MemorySpace>
bool is_structurally_symmetric(const cusp::csr_matrix<IndexType,ValueType,MemorySpace>& graph)
{
    if (graph.num_rows != graph.num_cols)
        return false;

    //Compute B = A^T  (B will have sorted indices)
    cusp::csr_matrix<IndexType,ValueType,MemorySpace> graph_t;
    cusp::transpose(graph, graph_t);

    if ( graph_t.row_offsets != graph.row_offsets )
        return false;

    //Compute B = A^T  (B will have sorted indices)
    cusp::csr_matrix<IndexType,ValueType,MemorySpace> graph_t_t;
    cusp::transpose(graph_t, graph_t_t);

    if ( graph_t.column_indices != graph_t_t.column_indices )
        return false;

    return true;
}

template< typename Array, typename PermMatrix >
void partitionToPermMatrix( const Array& partition, PermMatrix& P )
{
    typedef typename PermMatrix::index_type IndexType;

    int size = partition.size();

    Array sorted_part(partition);
    Array sequence(size);
    P.resize(size);

    thrust::sequence(sequence.begin(), sequence.end());
    thrust::stable_sort_by_key(sorted_part.begin(), sorted_part.end(), sequence.begin());
    thrust::scatter( thrust::counting_iterator<IndexType>(0), 
		     thrust::counting_iterator<IndexType>(size),
		     sequence.begin(),
		     P.values.begin());
}


} // end namespace graph
} // end namespace cusp

#include <cusp/graph/detail/partition.inl>
